package chapter04_RecursionAndDynamic;

import jdk.nashorn.internal.ir.ReturnNode;

import javax.swing.*;
import java.nio.channels.InterruptedByTimeoutException;

/**
 * 描述：
 *      换钱的方法数，给定一个arr数组，arr中值为正数且不重复，代表货币的面值类型，每种货币可以使用任意张
 *      给定一个aim代表要找的钱数，arr求换钱的方法有多少中
 * @author hl
 * @date 2021/6/5 9:22
 */
public class Coins {
    public static void main(String[] args) {
        int[] arr = {5, 10, 25, 1};
        int aim = 15;
        int i = coins1(arr, aim);
        int i2 = coins2(arr, aim);
        int i3 = coins3(arr, aim);
        int i4 = coins4(arr, aim);
        int i5 = coins5(arr, aim);
        System.out.println(i);
        System.out.println(i2);
        System.out.println(i3);
        System.out.println(i4);
        System.out.println(i5);
    }
    public static int coins1(int[] arr, int aim){
        if(arr == null || arr.length == 0 || aim < 0){
            return -1;
        }
        return process1(arr, 0, aim);
    }

    /**
     * 暴力递归：
     * 递归函数的含义是：返回arr[index ~ N-1]这些面值的钱组成aim的总方法数
     * 指定使用货币种类的范围，避免出现元素完全相同，但顺序不同的组合被加入到答案中
     * 时间复杂度最差情况下为O(aim ^ N)
     * @param arr
     * @param index
     * @param aim
     * @return
     */
    private static int process1(int[] arr, int index, int aim) {
        int res = 0;
        if (index == arr.length) {
            res = aim == 0 ? 1 : 0;
        }else{
            //遍历arr[index]可用的所有可能性，后序不再使用arr[index]
            for (int i = 0; arr[index] * i <= aim; i++) {
                res += process1(arr, index + 1, aim - arr[index] * i);
            }
        }
        return res;
    }

    public static int coins2(int[] arr, int aim){
        if (arr == null || arr.length == 0 || aim < 0) {
            return -1;
        }
        int[][] map = new int[arr.length + 1][aim + 1];
        return process2(arr, 0, aim, map);
    }

    /**
     * 记忆搜索：
     *      保利递归中存在大量重复的计算，我们可以将已经进行的递归过程以及其结果进行记录，后序遇到相同的递归过程直接得到结果
     *      记忆搜索可以避免重复的递归过程
     *      map中的值的含义：根据两个维度记录结果，也就是递归函数中变化的参数，index和aim，表示index和aim相同的递归过程
     *      map[i][j] = 0，这个递归未进行过，map[i][j] = -1表示这个递归进行过但结果为0，map[0][0]为0
     * 时间复杂度O(N * aim^2)
     * @param arr
     * @param index
     * @param aim
     * @param map
     * @return
     */
    private static int process2(int[] arr, int index, int aim, int[][] map) {
        int res = 0;
        if (index == arr.length) {
            res = aim == 0 ? 1 : 0;
        }else{
            int temp = 0;
            int mapV = 0;
            for (int i = 0; arr[index] * i <= aim; i++) {
                temp = aim - arr[index] * i;
                mapV = map[index + 1][temp];
                if (mapV != 0) {
                    //mapV == -1,表示计算过，但结果为0
                    res += mapV == -1 ? 0 : mapV;
                }else {
                    res += process2(arr, index + 1, temp, map);
                }

            }
        }
        map[index][aim] = res == 0 ? -1 : res;
        return res;
    }

    /**
     * 等价记忆搜索的动态规划
     * 创建一个i * j的矩阵，表示下标0~i的货币组成j的可能性
     * 矩阵的第一列dp[...][0]表示组成钱数为0的方法数，明显是1
     * dp[i][j]的值来自于两个地方：
     *      1)完全不使用货币i的情况，dp[i-1][j]
     *      2)使用1张货币i的可能性，res1 = dp[i -1][j - arr[i] * 1];
     *      使用2张货币i的可能性，dp[i -1][j - arr[i] * 2];
     *      使用k张货币i的可能性，dp[i -1][j - arr[i] * k],(arr[i]*k <= j);
     * 时间复杂度为O(N * aim^2)
     *
     * 可以看到记忆搜索其实是等价于这种方式的动态规划
     * @param arr
     * @param aim
     * @return
     */
    public static int coins3(int[] arr, int aim){
        if (arr == null || arr.length == 0 || aim < 0) {
            return -1;
        }
        int n = arr.length;
        int[][] dp = new int[n][aim + 1];
        for (int i = 0; i < n; i++) {
            dp[i][0] = 1;
        }
        for (int j = 1; j * arr[0] <= aim; j++) {
            dp[0][j * arr[0]] = 1;
        }
        int num = 0;
        for (int i = 1; i < n; i++) {
            for (int j = 1; j <= aim; j++) {
                num = 0;
                for (int k = 0; arr[i] * k <= j; k++) {
                    num += dp[i - 1][j - arr[i] * k];
                }
                dp[i][j] = num;
            }
        }
        return dp[n - 1][aim];
    }

    /**
     * 利用动态规划可以自定义计算顺序的优势，定义好计算的顺序，优化时间复杂度为O(N & aim)
     * 使用k张货币i的可能性，dp[i -1][j - arr[i] * k],(arr[i]*k <= j)的值其实就等于dp[i][j - arr[i]](j >= arr[i])
     * @param arr
     * @param aim
     * @return
     */
    public static int coins4(int[] arr, int aim){
        if (arr == null || arr.length == 0 || aim < 0) {
            return -1;
        }
        int n = arr.length;
        int[][] dp = new int[n][aim + 1];
        for (int i = 0; i < n; i++) {
            dp[i][0] = 1;
        }
        for (int j = 0; j * arr[0] <= aim; j++) {
            dp[0][j * arr[0]] = 1;
        }
        for (int i = 1; i < n; i++) {
            for (int j = 1; j <= aim; j++) {
                dp[i][j] = dp[i - 1][j];
                dp[i][j] += j >= arr[i] ? dp[i][j - arr[i]] : 0;
            }
        }
        return dp[n - 1][aim];
    }

    /**
     * 基于coins4进行空间压缩
     * @param arr
     * @param aim
     * @return
     */
    public static int coins5(int[] arr, int aim){
        if (arr == null || arr.length == 0 || aim < 0) {
            return -1;
        }
        int n = arr.length;
        int[] dp = new int[aim + 1];
        dp[0] = 1;
        for (int j = 1; j * arr[0] <= aim; j++) {
            dp[j * arr[0]] = 1;
        }
        for (int i = 1; i < n; i++) {
            for (int j = 1; j <= aim; j++) {
                dp[j] += j >= arr[i] ? dp[j - arr[i]] : 0;
            }
        }
        return dp[aim];
    }
}
